package my;

import java.util.Arrays;

/**
 * 贪心 - 加勒比海盗(最优装载问题)
 *
 * @author AJun
 * @date 2020/11/25
 */
public class Pirate {

    public static void main(String[] args) {
        int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};
        int capacity = 30;
        int count = new Pirate().optCount(weights, capacity);
        System.out.println("一共选了" + count + "件古董");
    }

    public int optCount(int[] weights, int capacity) {
        Arrays.sort(weights);
        // 已经装载重量
        int weight = 0;
        // 已经装载多少件
        int count = 0;

        for (int i = 0; i < weights.length && weight < capacity; i++) {
            int newWeight = weight + weights[i];
            if (newWeight <= capacity) {
                weight = newWeight;
                count++;
                System.out.println(weights[i]);
            }
        }
        return count;
    }

}
